home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1994 January / PSL Monthly Shareware CD-ROM (Public Software Library) (January 1994).iso / games / dos / puzzles / lptmaze.com / LPTMAZE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1991-04-07  |  41.2 KB  |  1,102 lines
  1. /*
  2.          This program will generate a three dimensional maze suitable for
  3.     printing on any printer giving 66 lines to a page that can print the
  4.     characters ".", "-", "+", and "#".  A different random number seed will
  5.     produce a different maze.
  6.  
  7.          Written by James L. Dean
  8.                     406 40th Street
  9.                     New Orleans, LA 70124-1532
  10. */
  11.  
  12. #include <stdio.h>
  13. #include <stdlib.h>
  14. #include <string.h>
  15. #include <malloc.h>
  16. #include <conio.h>
  17. #include <math.h>
  18.  
  19. #define TRUE 1
  20. #define FALSE 0
  21.  
  22. #define PAGE_WIDTH_IN_INCHES    8.0 /* LENGTH OF A LINE OF PRINT */
  23. #define PAGE_WIDTH_IN_SPACES   80
  24. #define WIDTH_IN_PAGES          6
  25. #define WIDTH_IN_INCHES        48.0 /* WIDTH_IN_PAGES*PAGE_WIDTH_IN_INCHES */
  26. #define NUM_Y_DOTS            480   /* WIDTH_IN_PAGES*PAGE_WIDTH_IN_SPACES */
  27. #define Y_DOT_MAX             479   /* NUM_Y_DOTS-1 */
  28. #define PAGE_LENGTH_IN_INCHES  11.0
  29. #define PAGE_LENGTH_IN_SPACES  66
  30. #define LENGTH_IN_PAGES         6
  31. #define LENGTH_IN_INCHES       66.0 /* LENGTH_IN_PAGES*PAGE_LENGTH_IN_INCHES */
  32. #define NUM_X_DOTS            396   /* LENGTH_IN_PAGES*PAGE_LENGTH_IN_SPACES */
  33. #define X_DOT_MAX             395   /* NUM_X_DOTS-1 */
  34. #define MIN_DOTS_PER_ROOM_WALL 40
  35. #define NUM_COLUMNS             9 /* <= NUM_X_DOTS/MIN_DOTS_PER_ROOM_WALL */
  36. #define MAX_X                  18 /* 2*NUM_COLUMNS */
  37. #define MAX_X_PLUS_1           19 /* MAX_X+1 */
  38. #define NUM_ROWS               12 /* <= NUM_Y_DOTS/MIN_DOTS_PER_ROOM_WALL */
  39. #define MAX_Y                  24 /* 2*NUM_ROWS */
  40. #define MAX_Y_PLUS_1           25 /* MAX_Y+1 */
  41. #define NUM_ROOMS_IN_MAZE     108 /* NUM_COLUMNS*NUM_ROWS */
  42.  
  43. typedef struct pointtype_record
  44.           {
  45.             int x;
  46.             int y;
  47.           } pointtype;
  48.  
  49. typedef struct prime_rec_record  *prime_rec_ptr;
  50.  
  51. typedef struct prime_rec_record
  52.           {
  53.             double        x;
  54.             double        y;
  55.             double        z;
  56.             char          base_z;
  57.             prime_rec_ptr left;
  58.             prime_rec_ptr right;
  59.             prime_rec_ptr down;
  60.             prime_rec_ptr lesser_x;
  61.             prime_rec_ptr greater_x;
  62.           } prime_rec;
  63.  
  64. typedef struct stack_rec_record  *stack_rec_ptr;
  65.  
  66. typedef struct stack_rec_record
  67.           {
  68.             char          index_1;
  69.             char          index_2;
  70.             stack_rec_ptr next_ptr;
  71.           } stack_rec;
  72.  
  73. typedef struct up_rec_record    *up_rec_ptr;
  74.  
  75. typedef struct up_rec_record
  76.           {
  77.             prime_rec_ptr up;
  78.             up_rec_ptr    next;
  79.             up_rec_ptr    previous;
  80.           } up_rec;
  81.  
  82. static void   add_room(void);
  83. static void   adjust_perspective(prime_rec_ptr *,prime_rec_ptr *,
  84.                prime_rec_ptr *,double *,double *,double *,double *,double *,
  85.                int *);
  86. static void   draw_line(int *,int *,int *,int *,char);
  87. static void   evaluate_and_transform(double *,double *,double *,double *,int *,
  88.                int *,double *,double *,prime_rec_ptr *,prime_rec_ptr *,
  89.                prime_rec_ptr *,double *,double *,double *,double *,double *,
  90.                int *);
  91. static double f(double,double);
  92.        void   main(void);
  93. static void   plot(prime_rec_ptr *,double *,double *,double *,double *,int *,
  94.                int *,double *,FILE **);
  95. static void   pset(int *,int *,char);
  96.  
  97. static int    delta_x [4] [24];
  98. static int    delta_y [4] [24];
  99. static char   *line_ptr [NUM_X_DOTS];
  100. static char   page [MAX_Y_PLUS_1] [MAX_X_PLUS_1];
  101. static int    r_n [8];
  102. static int    r_n_index_1;
  103. static int    r_n_index_2;
  104. static int    tem_int;
  105. static int    x;
  106. static double x_max;
  107. static int    x_next;
  108. static int    x_wall;
  109. static int    y;
  110. static int    y_next;
  111. static int    y_wall;
  112.  
  113. void main(void)
  114.     {
  115.       static   double        aspect_ratio;
  116.       static   int           column_num;
  117.       static   int           delta_index_1a;
  118.       static   int           delta_index_1b;
  119.       static   int           delta_index_1c;
  120.       static   int           delta_index_1d;
  121.       static   int           delta_index_2;
  122.       static   int           digit;
  123.       static   int           digit_num;
  124.       static   int           ending_column;
  125.       static   int           fatal_error;
  126.       static   int           line_num;
  127.       static   int           max_y_out;
  128.       static   int           max_z_out;
  129.                FILE          *maze;
  130.       static   int           num_x_divisions;
  131.       static   int           num_y_divisions;
  132.       static   int           page_num;
  133.       static   prime_rec_ptr prime_cornor;
  134.       static   prime_rec_ptr prime_head;
  135.       static   prime_rec_ptr prime_ptr;
  136.       static   prime_rec_ptr prime_tail;
  137.       static   double        rotation;
  138.       static   char          *row_ptr;
  139.       static   char          seed [256];
  140.       static   int           seed_length;
  141.       static   int           starting_column;
  142.       static   int           sum;
  143.       static   double        tilt;
  144.       static   double        x_min;
  145.       static   int           x_out;
  146.       static   double        x_prime_max;
  147.       static   double        y_max;
  148.       static   double        y_min;
  149.       static   int           y_out;
  150.       static   double        y_prime_max;
  151.       static   double        y_prime_min;
  152.       static   double        z_prime_max;
  153.       static   double        z_prime_min;
  154.                              
  155.       fatal_error=FALSE;
  156.       printf("\n     This program takes a \"photograph\" of a three ");
  157.       printf("dimensional maze.  To print\n");
  158.       printf("the photograph from the \"negative\", print the file ");
  159.       printf("LPTMAZE.LST.\n");
  160.       printf("\n     Random number seed? ");
  161.       fflush(stdin);
  162.       gets(&seed[0]);
  163.       seed_length=strlen(&seed[0]);
  164.       for (r_n_index_1=0; r_n_index_1 < seed_length; ++r_n_index_1)
  165.         {
  166.           tem_int=(int) seed[r_n_index_1];
  167.           while (tem_int >= 29)
  168.            tem_int-=29;
  169.           r_n[r_n_index_1]=tem_int;
  170.         }
  171.       r_n_index_2=7;
  172.       while (r_n_index_1 > 0)
  173.         {
  174.            r_n_index_1--;
  175.            r_n[r_n_index_2]=r_n[r_n_index_1];
  176.            r_n_index_2--;
  177.         }
  178.       while (r_n_index_2 >= 0)
  179.         {
  180.           r_n[r_n_index_2]=19;
  181.           r_n_index_2--;
  182.         }
  183.       printf("\n     Designing floor plan...\n");
  184.       delta_x[0][0]=-1;
  185.       delta_y[0][0]=0;
  186.       delta_x[1][0]=0;
  187.       delta_y[1][0]=1;
  188.       delta_x[2][0]=1;
  189.       delta_y[2][0]=0;
  190.       delta_x[3][0]=0;
  191.       delta_y[3][0]=-1;
  192.       delta_index_2=0;
  193.       for (delta_index_1a=0; delta_index_1a < 4; ++delta_index_1a)
  194.         for (delta_index_1b=0; delta_index_1b < 4; ++delta_index_1b)
  195.           if (delta_index_1a != delta_index_1b)
  196.             for (delta_index_1c=0; delta_index_1c < 4; ++delta_index_1c)
  197.               if ((delta_index_1a != delta_index_1c)
  198.               &&  (delta_index_1b != delta_index_1c))
  199.                 for (delta_index_1d=0; delta_index_1d < 4; ++delta_index_1d)
  200.                   if ((delta_index_1a != delta_index_1d)
  201.                   &&  (delta_index_1b != delta_index_1d)
  202.                   &&  (delta_index_1c != delta_index_1d))
  203.                     {
  204.                       delta_x[delta_index_1a][delta_index_2]=delta_x[0][0];
  205.                       delta_y[delta_index_1a][delta_index_2]=delta_y[0][0];
  206.                       delta_x[delta_index_1b][delta_index_2]=delta_x[1][0];
  207.                       delta_y[delta_index_1b][delta_index_2]=delta_y[1][0];
  208.                       delta_x[delta_index_1c][delta_index_2]=delta_x[2][0];
  209.                       delta_y[delta_index_1c][delta_index_2]=delta_y[2][0];
  210.                       delta_x[delta_index_1d][delta_index_2]=delta_x[3][0];
  211.                       delta_y[delta_index_1d][delta_index_2]=delta_y[3][0];
  212.                       delta_index_2++;
  213.                     }
  214.       max_y_out=X_DOT_MAX;
  215.       max_z_out=Y_DOT_MAX;
  216.       aspect_ratio=1.0/(LENGTH_IN_INCHES
  217.        *(((float) NUM_Y_DOTS)/((float) NUM_X_DOTS))/WIDTH_IN_INCHES);
  218.       for (y_out=0; y_out <= MAX_Y; ++y_out)
  219.         for (x_out=0; x_out <= MAX_X; ++x_out)
  220.           page[y_out][x_out]='W';
  221.       sum=0;
  222.       for (digit_num=1; digit_num <= 3; ++digit_num)
  223.         {
  224.           digit=r_n[0];
  225.           r_n_index_1=0;
  226.           for (r_n_index_2=1; r_n_index_2 < 8; ++r_n_index_2)
  227.             {
  228.               tem_int=r_n[r_n_index_2];
  229.               r_n[r_n_index_1]=tem_int;
  230.               digit+=tem_int;
  231.               if (digit >= 29)
  232.                  digit-=29;
  233.               r_n_index_1=r_n_index_2;
  234.             }
  235.           r_n[7]=digit;
  236.           sum=29*sum+digit;
  237.         }
  238.       x=2*(sum % NUM_COLUMNS)+1;
  239.       sum=0;
  240.       for (digit_num=1; digit_num <= 3; ++digit_num)
  241.         {
  242.           digit=r_n[0];
  243.           r_n_index_1=0;
  244.           for (r_n_index_2=1; r_n_index_2 < 8; ++r_n_index_2)
  245.             {
  246.               tem_int=r_n[r_n_index_2];
  247.               r_n[r_n_index_1]=tem_int;
  248.               digit+=tem_int;
  249.               if (digit >= 29)
  250.                  digit-=29;
  251.               r_n_index_1=r_n_index_2;
  252.             }
  253.           r_n[7]=digit;
  254.           sum=29*sum+digit;
  255.         }
  256.       y=2*(sum % NUM_ROWS)+1;
  257.       add_room();
  258.       page[0][1]=' ';
  259.       page[MAX_Y][MAX_X-1]=' ';
  260.       printf("\n     Building maze...\n");
  261.       x_min=1.0;
  262.       x_max=(double) MAX_Y;
  263.       x_max=2.0*x_max+5.0;
  264.       y_min=1.0;
  265.       y_max=(double) MAX_X;
  266.       y_max=2.0*y_max+5.0;
  267.       num_x_divisions=2*MAX_Y+5;
  268.       num_y_divisions=2*MAX_X+5;
  269.       prime_head=NULL;
  270.       rotation=20.0;
  271.       tilt=30.0;
  272.       evaluate_and_transform(&x_min,&x_max,&y_min,&y_max,
  273.        &num_x_divisions,&num_y_divisions,&rotation,&tilt,
  274.        &prime_cornor,&prime_head,&prime_tail,&x_prime_max,
  275.        &y_prime_min,&y_prime_max,&z_prime_min,&z_prime_max,
  276.        &fatal_error);
  277.       if (! fatal_error)
  278.         {
  279.           printf("\n     Photographing maze...\n");
  280.           adjust_perspective(&prime_cornor,&prime_head,&prime_tail,
  281.            &x_prime_max,&y_prime_min,&y_prime_max,&z_prime_min,
  282.            &z_prime_max,&fatal_error);
  283.         }
  284.       if (! fatal_error)
  285.         {
  286.           printf("\n     Developing film...\n");
  287.           for (line_num=0;  
  288.            ((! fatal_error) && (line_num < NUM_X_DOTS)); 
  289.            line_num++)
  290.             if ((row_ptr=(char *) malloc(NUM_Y_DOTS))
  291.              == NULL)
  292.               {
  293.                 fatal_error=TRUE;
  294.                 printf("\n     Fatal error:  out of memory\n");
  295.               }
  296.             else
  297.               {
  298.                 line_ptr[line_num]=row_ptr;
  299.                 for (column_num=0; column_num < NUM_Y_DOTS; 
  300.                  column_num++)
  301.                   *(row_ptr++)=' ';
  302.               }
  303.         }
  304.       if (! fatal_error)
  305.         {
  306.           plot(&prime_tail,&y_prime_min,&y_prime_max,
  307.            &z_prime_min,&z_prime_max,&max_y_out,&max_z_out,
  308.            &aspect_ratio,&maze);
  309.           maze=fopen("LPTMAZE.LST","w");
  310.           starting_column=0;
  311.           ending_column=PAGE_WIDTH_IN_SPACES-1;
  312.           for (page_num=1; page_num <= WIDTH_IN_PAGES; page_num++)
  313.             {
  314.               for (line_num=0; (line_num < NUM_X_DOTS); line_num++)
  315.                 {
  316.                   for (column_num=starting_column;
  317.                    column_num <= ending_column; column_num++)
  318.                     fputc((int) *((line_ptr[line_num])+column_num),maze);
  319.                   fputc((int) '\n',maze);
  320.                 }
  321.               starting_column+=PAGE_WIDTH_IN_SPACES;
  322.               ending_column+=PAGE_WIDTH_IN_SPACES;
  323.             }
  324.           fclose(maze);
  325.           for (line_num=0; ((! fatal_error) && (line_num < NUM_X_DOTS)); 
  326.            line_num++)
  327.             free (line_ptr[line_num]);
  328.           while (prime_head != NULL)
  329.             {
  330.               prime_ptr=prime_head->greater_x;
  331.               free(prime_head);
  332.               prime_head=prime_ptr;
  333.             }
  334.         }
  335.       if (! fatal_error)
  336.         printf("\n     To print the maze, \"PRINT LPTMAZE.LST\".\n");
  337.     }
  338.  
  339. static void add_room()
  340.     {
  341.       unsigned char delta_index_1;
  342.       unsigned char delta_index_2;
  343.  
  344.       page[y][x]=' ';
  345.       delta_index_1=0;
  346.       do
  347.         {
  348.           delta_index_2=(unsigned char) r_n[0];
  349.           r_n_index_1=0;
  350.           for (r_n_index_2=1; r_n_index_2 < 8; ++r_n_index_2)
  351.             {
  352.               tem_int=r_n[r_n_index_2];
  353.               r_n[r_n_index_1]=tem_int;
  354.               delta_index_2+=(unsigned char) tem_int;
  355.               if (delta_index_2 >= 29)
  356.                 delta_index_2-=29;
  357.               r_n_index_1=r_n_index_2;
  358.             }
  359.           r_n[7]=delta_index_2;
  360.         }
  361.       while (delta_index_2 >= 24);
  362.       while (delta_index_1 < 4)
  363.         {
  364.           x_next=x+2*delta_x[delta_index_1][delta_index_2];
  365.           if ((x_next <= 0) || (x_next >= MAX_X))
  366.             delta_index_1++;
  367.           else
  368.             {
  369.               y_next=y+2*delta_y[delta_index_1][delta_index_2];
  370.               if ((y_next <= 0) || (y_next >= MAX_Y))
  371.                 delta_index_1++;
  372.               else
  373.                 if ((page[y_next][x_next] == 'W'))
  374.                   {
  375.                     if (x == x_next)
  376.                       {
  377.                         y_wall=(y+y_next)/2;
  378.                         page[y_wall][x_next]=' ';
  379.                       }
  380.                     else
  381.                       {
  382.                         x_wall=(x+x_next)/2;
  383.                         page[y_next][x_wall]=' ';
  384.                       }
  385.                     x=x_next;
  386.                     y=y_next;
  387.                     add_room();
  388.                     x-=2*delta_x[delta_index_1][delta_index_2];
  389.                     y-=2*delta_y[delta_index_1][delta_index_2];
  390.                   }
  391.                 else
  392.                   delta_index_1++;
  393.             }
  394.         }
  395.     }
  396.  
  397. static double f(x,y)
  398.   double x;
  399.   double y;
  400.     {
  401.       register int    x_out;
  402.       register int    y_out;
  403.       static   double z;
  404.  
  405.       y_out=((int) x)-2;
  406.       if (y_out < 0)
  407.         z=0.0;
  408.       else
  409.         if (y_out > 2*MAX_Y+1)
  410.           z=0.0;
  411.         else
  412.           {
  413.             x_out=((int) y)-2;
  414.             if (x_out < 0)
  415.               z=0.0;
  416.             else
  417.               if (x_out > 2*MAX_X+1)
  418.                 z=0.0;
  419.               else
  420.                 if (page[y_out/2][x_out/2] == 'W')
  421.                   z=7.0;
  422.                 else
  423.                   z=0.0;
  424.           }
  425.       return(z);
  426.     }
  427.  
  428. static void evaluate_and_transform(x_min,x_max,y_min,y_max,num_x_divisions,
  429.  num_y_divisions,rotation,tilt,prime_cornor,prime_head,prime_tail,x_prime_max,
  430.  y_prime_min,y_prime_max,z_prime_min,z_prime_max,fatal_error)
  431.   double        *x_min;
  432.   double        *x_max;
  433.   double        *y_min;
  434.   double        *y_max;
  435.   int           *num_x_divisions;
  436.   int           *num_y_divisions;
  437.   double        *rotation;
  438.   double        *tilt;
  439.   prime_rec_ptr *prime_cornor;
  440.   prime_rec_ptr *prime_head;
  441.   prime_rec_ptr *prime_tail;
  442.   double        *x_prime_max;
  443.   double        *y_prime_min;
  444.   double        *y_prime_max;
  445.   double        *z_prime_min;
  446.   double        *z_prime_max;
  447.   int           *fatal_error;
  448.     {
  449.       static   double        cos_rotation;
  450.       static   double        cos_tilt;
  451.       static   double        delta_x;
  452.       static   double        delta_y;
  453.       static   prime_rec_ptr last_prime_ptr;
  454.       static   prime_rec_ptr prime_ptr;
  455.       static   double        radians;
  456.       static   double        radians_per_degree;
  457.       static   prime_rec_ptr left;
  458.       static   double        sin_rotation;
  459.       static   double        sin_tilt;
  460.       static   up_rec_ptr    up_head;
  461.       static   up_rec_ptr    up_ptr;
  462.       static   up_rec_ptr    up_tail;
  463.       static   double        x;
  464.       register int           x_division_num;
  465.       static   double        y;
  466.       register int           y_division_num;
  467.       static   double        x_rotated;
  468.       static   double        z;
  469.  
  470.       radians_per_degree=atan((double) 1.0)/45.0;
  471.       radians=(*tilt)*radians_per_degree;
  472.       cos_tilt=cos(radians);
  473.       sin_tilt=sin(radians);
  474.       radians=(*rotation)*radians_per_degree;
  475.       cos_rotation=cos(radians);
  476.       sin_rotation=sin(radians);
  477.       z=f(*x_min,*y_min);
  478.       x_rotated=(*x_min)*cos_rotation+(*y_min)*sin_rotation;
  479.       (*y_prime_min)=-(*x_min)*sin_rotation+(*y_min)*cos_rotation;
  480.       (*z_prime_min)=-x_rotated*sin_tilt+z*cos_tilt;
  481.       (*x_prime_max)=x_rotated*cos_tilt+z*sin_tilt;
  482.       (*y_prime_max)=(*y_prime_min);
  483.       (*z_prime_max)=(*z_prime_min);
  484.       last_prime_ptr=NULL;
  485.       delta_x=(double) (*num_x_divisions);
  486.       delta_x=((*x_max)-(*x_min))/delta_x;
  487.       delta_y=(double) (*num_y_divisions);
  488.       delta_y=((*y_max)-(*y_min))/delta_y;
  489.       up_head=NULL;
  490.       up_tail=NULL;
  491.       for (y_division_num=1;
  492.        ((y_division_num <= (*num_y_divisions)) && (! *fatal_error));
  493.        ++y_division_num)
  494.         {
  495.           if ((up_ptr=(up_rec *) malloc(sizeof(up_rec))) == NULL)
  496.             {
  497.               *fatal_error=TRUE;
  498.               printf("\n     Fatal error:  out of memory\n");
  499.             }
  500.           else
  501.             {
  502.               up_ptr->up=NULL;
  503.               if (up_head == NULL)
  504.                 {
  505.                   up_head=up_ptr;
  506.                   up_ptr->previous=NULL;
  507.                 }
  508.               else
  509.                 {
  510.                   up_tail->next=up_ptr;
  511.                   up_ptr->previous=up_tail;
  512.                 }
  513.               up_ptr->next=NULL;
  514.               up_tail=up_ptr;
  515.             }
  516.         }
  517.       x=(*x_min);
  518.       for (x_division_num=1;
  519.        ((x_division_num <= (*num_x_divisions)) && (! *fatal_error));
  520.        ++x_division_num)
  521.         {
  522.           left=NULL;
  523.           up_ptr=up_head;
  524.           y=(*y_min);
  525.           for (y_division_num=1;
  526.            ((y_division_num <= (*num_y_divisions)) && (! *fatal_error));
  527.            ++y_division_num)
  528.             {
  529.               z=f(x,y);
  530.               if ((prime_ptr=(prime_rec *) malloc(sizeof(prime_rec)))
  531.                == NULL)
  532.                 {
  533.                   *fatal_error=TRUE;
  534.                   printf("\n     Fatal error:  out of memory\n");
  535.                 }
  536.               else
  537.                 {
  538.                   prime_ptr->left=left;
  539.                   if (z > 0.0)
  540.                     prime_ptr->base_z=(char) 1;
  541.                   else
  542.                     prime_ptr->base_z=(char) 0;
  543.                   if (left != NULL)
  544.                     left->right=prime_ptr;
  545.                   if (up_ptr->up != NULL)
  546.                     up_ptr->up->down=prime_ptr;
  547.                   x_rotated=x*cos_rotation+y*sin_rotation;
  548.                   prime_ptr->y=-x*sin_rotation+y*cos_rotation;
  549.                   prime_ptr->x=x_rotated*cos_tilt+z*sin_tilt;
  550.                   prime_ptr->z=-x_rotated*sin_tilt+z*cos_tilt;
  551.                   if (prime_ptr->x > (*x_prime_max))
  552.                     (*x_prime_max)=prime_ptr->x;
  553.                   if (prime_ptr->y < (*y_prime_min))
  554.                     (*y_prime_min)=prime_ptr->y;
  555.                   if (prime_ptr->y > (*y_prime_max))
  556.                     (*y_prime_max)=prime_ptr->y;
  557.                   if (prime_ptr->z < (*z_prime_min))
  558.                     (*z_prime_min)=prime_ptr->z;
  559.                   if (prime_ptr->z > (*z_prime_max))
  560.                     (*z_prime_max)=prime_ptr->z;
  561.                   prime_ptr->lesser_x=NULL;
  562.                   if (last_prime_ptr == NULL)
  563.                     {
  564.                       (*prime_tail)=prime_ptr;
  565.                       (*prime_cornor)=prime_ptr;
  566.                       prime_ptr->greater_x=NULL;
  567.                     }
  568.                   else
  569.                     {
  570.                       (*prime_head)->lesser_x=prime_ptr;
  571.                       prime_ptr->greater_x=(*prime_head);
  572.                     }
  573.                   (*prime_head)=prime_ptr;
  574.                   left=prime_ptr;
  575.                   up_ptr->up=prime_ptr;
  576.                   up_ptr=up_ptr->next;
  577.                   last_prime_ptr=prime_ptr;
  578.                   y+=delta_y;
  579.                 }
  580.             }
  581.           if (! *fatal_error)
  582.             {
  583.               left->right=NULL;
  584.               x+=delta_x;
  585.             }
  586.         }
  587.       if (! *fatal_error)
  588.         while (up_head != NULL)
  589.           {
  590.             up_head->up->down=NULL;
  591.             up_ptr=up_head->next;
  592.             free(up_head);
  593.             up_head=up_ptr;
  594.           }
  595.     }
  596.  
  597. static void adjust_perspective(prime_cornor,prime_head,prime_tail,x_prime_max,
  598.  y_prime_min,y_prime_max,z_prime_min,z_prime_max,fatal_error)
  599.   prime_rec_ptr *prime_cornor;
  600.   prime_rec_ptr *prime_head;
  601.   prime_rec_ptr *prime_tail;
  602.   double        *x_prime_max;
  603.   double        *y_prime_min;
  604.   double        *y_prime_max;
  605.   double        *z_prime_min;
  606.   double        *z_prime_max;
  607.   int           *fatal_error;
  608.     {
  609.       static   double        delta_x;
  610.       static   double        delta_y;
  611.       static   double        delta_z;
  612.       register int           finished;
  613.       static   prime_rec_ptr last_prime_ptr;
  614.       static   prime_rec_ptr left;
  615.       static   prime_rec_ptr new_prime_head;
  616.       static   prime_rec_ptr new_prime_ptr;
  617.       static   prime_rec_ptr new_prime_tail;
  618.       static   prime_rec_ptr next_prime_row;
  619.       static   prime_rec_ptr prime_column;
  620.       static   prime_rec_ptr prime_ptr;
  621.       static   prime_rec_ptr prime_row;
  622.       static   up_rec_ptr    up_head;
  623.       static   up_rec_ptr    up_ptr;
  624.       static   up_rec_ptr    up_tail;
  625.       static   double        x_eye;
  626.       static   double        y_center;
  627.       static   double        z_center;
  628.  
  629.       if (((*y_prime_max)-(*y_prime_min)) > ((*z_prime_max)-(*z_prime_min)))
  630.         x_eye=2.0*((*y_prime_max)-(*y_prime_min))+(*x_prime_max);
  631.       else
  632.         x_eye=2.0*((*z_prime_max)-(*z_prime_min))+(*x_prime_max);
  633.       if (x_eye != (*x_prime_max))
  634.         {
  635.           up_head=NULL;
  636.           up_tail=NULL;
  637.           prime_column=(*prime_cornor);
  638.           while ((prime_column != NULL) && (! *fatal_error))
  639.             {
  640.               if ((up_ptr=(up_rec *) malloc(sizeof(up_rec))) == NULL)
  641.                 {
  642.                   *fatal_error=TRUE;
  643.                   printf("\n     Fatal error:  out of memory\n");
  644.                 }
  645.               else
  646.                 {
  647.                   up_ptr->up=NULL;
  648.                   if (up_head == NULL)
  649.                     {
  650.                       up_head=up_ptr;
  651.                       up_ptr->previous=NULL;
  652.                     }
  653.                   else
  654.                     {
  655.                       up_tail->next=up_ptr;
  656.                       up_ptr->previous=up_tail;
  657.                     }
  658.                   up_ptr->next=NULL;
  659.                   up_tail=up_ptr;
  660.                   prime_column=prime_column->right;
  661.                 }
  662.             }
  663.           y_center=(double) ((*y_prime_max)+(*y_prime_min))/2.0;
  664.           z_center=(double) ((*z_prime_max)+(*z_prime_min))/2.0;
  665.           last_prime_ptr=NULL;
  666.           new_prime_head=NULL;
  667.           new_prime_tail=NULL;
  668.           prime_row=(*prime_cornor);
  669.           while ((prime_row != NULL) && (! *fatal_error))
  670.             {
  671.               left=NULL;
  672.               up_ptr=up_head;
  673.               next_prime_row=prime_row->down;
  674.               prime_column=prime_row;
  675.               while ((prime_column != NULL) && (! *fatal_error))
  676.                 {
  677.                   if ((new_prime_ptr=(prime_rec *) malloc(sizeof(prime_rec)))
  678.                    == NULL)
  679.                     {
  680.                       *fatal_error=TRUE;
  681.                       printf("\n     Fatal error:  out of memory\n");
  682.                     }
  683.                   else
  684.                     {
  685.                       new_prime_ptr->left=left;
  686.                       new_prime_ptr->base_z=prime_column->base_z;
  687.                       if (left != NULL)
  688.                         left->right=new_prime_ptr;
  689.                       if (up_ptr->up != NULL)
  690.                         up_ptr->up->down=new_prime_ptr;
  691.                       delta_x=prime_column->x-x_eye;
  692.                       delta_y=prime_column->y-y_center;
  693.                       delta_z=prime_column->z-z_center;
  694.                       new_prime_ptr->x
  695.                        =sqrt(delta_x*delta_x+delta_y*delta_y+delta_z*delta_z);
  696.                       new_prime_ptr->y
  697.                        =y_center+(double)(prime_column->y-y_center)
  698.                        *(x_eye-(*x_prime_max))/(x_eye-prime_column->x);
  699.                       new_prime_ptr->z
  700.                        =z_center+(double)(prime_column->z-z_center)
  701.                        *(x_eye-(*x_prime_max))/(x_eye-prime_column->x);
  702.                       if (last_prime_ptr == NULL)
  703.                         {
  704.                           new_prime_head=new_prime_ptr;
  705.                           new_prime_tail=new_prime_ptr;
  706.                           new_prime_ptr->lesser_x=NULL;
  707.                           new_prime_ptr->greater_x=NULL;
  708.                         }
  709.                       else
  710.                         if (new_prime_ptr->x < last_prime_ptr->x)
  711.                           {
  712.                             finished=FALSE;
  713.                             while (! finished)
  714.                               {
  715.                                 last_prime_ptr=last_prime_ptr->lesser_x;
  716.                                 if (last_prime_ptr == NULL)
  717.                                   finished=TRUE;
  718.                                 else
  719.                                   {
  720.                                     if (new_prime_ptr->x >= last_prime_ptr->x)
  721.                                       finished=TRUE;
  722.                                   }
  723.                               }
  724.                             new_prime_ptr->lesser_x=last_prime_ptr;
  725.                             if (last_prime_ptr == NULL)
  726.                               {
  727.                                 new_prime_head->lesser_x=new_prime_ptr;
  728.                                 new_prime_ptr->greater_x=new_prime_head;
  729.                                 new_prime_head=new_prime_ptr;
  730.                               }
  731.                             else
  732.                               {
  733.                                 new_prime_ptr->greater_x
  734.                                  =last_prime_ptr->greater_x;
  735.                                 last_prime_ptr->greater_x->lesser_x
  736.                                  =new_prime_ptr;
  737.                                 last_prime_ptr->greater_x=new_prime_ptr;
  738.                               }
  739.                           }
  740.                         else
  741.                           {
  742.                             finished=FALSE;
  743.                             while (! finished)
  744.                               {
  745.                                 last_prime_ptr=last_prime_ptr->greater_x;
  746.                                 if (last_prime_ptr == NULL)
  747.                                   finished=TRUE;
  748.                                 else
  749.                                   {
  750.                                     if (new_prime_ptr->x <= last_prime_ptr->x)
  751.                                       finished=TRUE;
  752.                                   }
  753.                               }
  754.                             new_prime_ptr->greater_x=last_prime_ptr;
  755.                             if (last_prime_ptr == NULL)
  756.                               {
  757.                                 new_prime_tail->greater_x=new_prime_ptr;
  758.                                 new_prime_ptr->lesser_x=new_prime_tail;
  759.                                 new_prime_tail=new_prime_ptr;
  760.                               }
  761.                             else
  762.                               {
  763.                                 new_prime_ptr->lesser_x
  764.                                  =last_prime_ptr->lesser_x;
  765.                                 last_prime_ptr->lesser_x->greater_x
  766.                                  =new_prime_ptr;
  767.                                 last_prime_ptr->lesser_x=new_prime_ptr;
  768.                               }
  769.                           }
  770.                     }
  771.                   if (! *fatal_error)
  772.                     {
  773.                       left=new_prime_ptr;
  774.                       up_ptr->up=new_prime_ptr;
  775.                       up_ptr=up_ptr->next;
  776.                       last_prime_ptr=new_prime_ptr;
  777.                       prime_ptr=prime_column->right;
  778.                       free(prime_column);
  779.                       prime_column=prime_ptr;
  780.                     }
  781.                 }
  782.               if (! *fatal_error)
  783.                 {
  784.                   left->right=NULL;
  785.                   prime_row=next_prime_row;
  786.                 }
  787.             }
  788.           if (! *fatal_error)
  789.             {
  790.               (*prime_head)=new_prime_head;
  791.               (*prime_tail)=new_prime_tail;
  792.               while (up_head != NULL)
  793.                 {
  794.                   up_head->up->down=NULL;
  795.                   up_ptr=up_head->next;
  796.                   free(up_head);
  797.                   up_head=up_ptr;
  798.                 }
  799.             }
  800.         }
  801.     }
  802.  
  803. static void pset(x,y,shading)
  804.   int  *x;
  805.   int  *y;
  806.   char shading;
  807.     {
  808.       *((line_ptr[*x])+(Y_DOT_MAX-(*y)))=shading;
  809.     }
  810.  
  811. static void draw_line(x1,y1,x2,y2,shading)
  812.   int  *x1;
  813.   int  *y1;
  814.   int  *x2;
  815.   int  *y2;
  816.   char shading;
  817.     {
  818.       static   int error;
  819.       static   int error_prime_x;
  820.       static   int error_prime_y;
  821.       register int permissible_delta_x;
  822.       register int permissible_delta_y;
  823.       static   int x;
  824.       static   int x_diff;
  825.       static   int y;
  826.       static   int y_diff;
  827.  
  828.       if ((*x2) >= (*x1))
  829.         permissible_delta_x=1;
  830.       else
  831.         permissible_delta_x=-1;
  832.       if ((*y2) >= (*y1))
  833.         permissible_delta_y=1;
  834.       else
  835.         permissible_delta_y=-1;
  836.       x=(*x1);
  837.       y=(*y1);
  838.       x_diff=(*x2)-(*x1);
  839.       y_diff=(*y2)-(*y1);
  840.       error=0;
  841.       pset(&x,&y,shading);
  842.       while ((x != (*x2)) || (y != (*y2)))
  843.         {
  844.           error_prime_x=error+permissible_delta_x*y_diff;
  845.           error_prime_y=error-permissible_delta_y*x_diff;
  846.           if (abs(error_prime_x) <= abs(error_prime_y))
  847.             {
  848.               x+=permissible_delta_x;
  849.               error=error_prime_x;
  850.             }
  851.           else
  852.             {
  853.               y+=permissible_delta_y;
  854.               error=error_prime_y;
  855.             }
  856.           pset(&x,&y,shading);
  857.         }
  858.     }
  859.  
  860. static void plot(prime_tail,y_prime_min,y_prime_max,z_prime_min,z_prime_max,
  861.  max_y_out,max_z_out,aspect_ratio,maze)
  862.   prime_rec_ptr *prime_tail;
  863.   double *y_prime_min;
  864.   double *y_prime_max;
  865.   double *z_prime_min;
  866.   double *z_prime_max;
  867.   int    *max_y_out;
  868.   int    *max_z_out;
  869.   double *aspect_ratio;
  870.   FILE   **maze;
  871.     {
  872.       static   pointtype     box [4];
  873.       static   long          box_delta_x;
  874.       static   long          box_delta_y;
  875.       register int           box_num_1;
  876.       register int           box_num_2;
  877.       static   long          box_x_intercept;
  878.       static   int           box_x1;
  879.       static   int           box_x2;
  880.       static   int           box_y_max;
  881.       static   int           box_y_min;
  882.       static   long          box_y_offset;
  883.       static   int           box_y1;
  884.       static   int           intercept_count_mod_2;
  885.       static   int           line_x1;
  886.       static   int           line_x2;
  887.       static   int           line_y1;
  888.       static   int           line_y2;
  889.       static   double        pixels_per_unit;
  890.       static   prime_rec_ptr prime_ptr;
  891.       static   char          shading;
  892.       static   double        y_offset;
  893.       static   double        y_out_max;
  894.       static   double        z_offset;
  895.       static   double        z_out_max;
  896.  
  897.       y_out_max=(double) (*max_y_out);
  898.       z_out_max=(double) (*max_z_out);
  899.       if ((*aspect_ratio)*z_out_max*((*y_prime_max)-(*y_prime_min))
  900.        > y_out_max*((*z_prime_max)-(*z_prime_min)))
  901.         {
  902.           pixels_per_unit
  903.            =y_out_max/((*aspect_ratio)*((*y_prime_max)-(*y_prime_min)));
  904.           y_offset=0.0;
  905.           z_offset
  906.            =-(z_out_max-pixels_per_unit*((*z_prime_max)-(*z_prime_min)))/2.0;
  907.         }
  908.       else
  909.         if ((*aspect_ratio)*z_out_max*((*y_prime_max)-(*y_prime_min))
  910.          < y_out_max*((*z_prime_max)-(*z_prime_min)))
  911.           {
  912.             pixels_per_unit=z_out_max/((*z_prime_max)-(*z_prime_min));
  913.             y_offset=(y_out_max
  914.              -(*aspect_ratio)*pixels_per_unit*((*y_prime_max)-(*y_prime_min)))/2.0;
  915.             z_offset=0.0;
  916.           }
  917.         else
  918.           /* plot degenerates to a single point */
  919.           {
  920.             pixels_per_unit=1.0;
  921.             y_offset=y_out_max/2.0;
  922.             z_offset=-z_out_max/2.0;
  923.           }
  924.       prime_ptr=(*prime_tail);
  925.       while ((prime_ptr != NULL))
  926.         {
  927.           if ((prime_ptr->right != NULL))
  928.             {
  929.               if ((prime_ptr->down != NULL))
  930.                 {
  931.                   box[0].x=(int) (y_offset+pixels_per_unit
  932.                    *(*aspect_ratio)*(prime_ptr->y-(*y_prime_min)));
  933.                   box[0].y=(int) (z_offset+z_out_max-pixels_per_unit
  934.                    *(prime_ptr->z-(*z_prime_min)));
  935.                   box[1].x=(int) (y_offset+pixels_per_unit
  936.                    *(*aspect_ratio)*(prime_ptr->right->y-(*y_prime_min)));
  937.                   box[1].y=(int) (z_offset+z_out_max-pixels_per_unit
  938.                    *(prime_ptr->right->z-(*z_prime_min)));
  939.                   box[3].x=(int) (y_offset+pixels_per_unit
  940.                    *(*aspect_ratio)*(prime_ptr->down->y-(*y_prime_min)));
  941.                   box[3].y=(int) (z_offset+z_out_max-pixels_per_unit
  942.                    *(prime_ptr->down->z-(*z_prime_min)));
  943.                   box[2].x=(int) (y_offset+pixels_per_unit
  944.                    *(*aspect_ratio)*(prime_ptr->down->right->y-(*y_prime_min)));
  945.                   box[2].y=(int) (z_offset+z_out_max-pixels_per_unit
  946.                    *(prime_ptr->down->right->z-(*z_prime_min)));
  947.                   box_y_min=box[0].y;
  948.                   box_y_max=box_y_min;
  949.                   if ((prime_ptr->base_z == (char) 1)
  950.                   &&  (prime_ptr->right->base_z == (char) 1)
  951.                   &&  (prime_ptr->down->base_z == (char) 1)
  952.                   &&  (prime_ptr->down->right->base_z == (char) 1)) 
  953.                     shading='.';
  954.                   else
  955.                     if ((prime_ptr->base_z == (char) 0)
  956.                     &&  (prime_ptr->right->base_z == (char) 0)
  957.                     &&  (prime_ptr->down->base_z == (char) 0)
  958.                     &&  (prime_ptr->down->right->base_z == (char) 0)) 
  959.                       shading='-';
  960.                     else
  961.                       if ((prime_ptr->base_z == (char) 1)
  962.                       &&  (prime_ptr->right->base_z == (char) 1)
  963.                       &&  (prime_ptr->down->base_z == (char) 0)
  964.                       &&  (prime_ptr->down->right->base_z == (char) 0)) 
  965.                         shading='+';
  966.                       else
  967.                         if ((prime_ptr->base_z == (char) 1)
  968.                         &&  (prime_ptr->right->base_z == (char) 0)
  969.                         &&  (prime_ptr->down->base_z == (char) 1)
  970.                         &&  (prime_ptr->down->right->base_z == (char) 0)) 
  971.                           shading='#';
  972.                         else
  973.                           if ((prime_ptr->down->down == NULL)
  974.                           &&  (prime_ptr->base_z == (char) 0)) 
  975.                             shading='-';
  976.                           else
  977.                             shading='+';
  978.                   for (box_num_1=1; box_num_1 < 4; ++box_num_1)
  979.                     {
  980.                       if (box[box_num_1].y < box_y_min)
  981.                         box_y_min=box[box_num_1].y;
  982.                       if (box[box_num_1].y > box_y_max)
  983.                         box_y_max=box[box_num_1].y;
  984.                     }
  985.                   for (box_y1=box_y_min; box_y1 <= box_y_max; ++box_y1)
  986.                     {
  987.                       intercept_count_mod_2=0;
  988.                       box_num_2=1;
  989.                       for (box_num_1=0; box_num_1 < 4; ++box_num_1)
  990.                         {
  991.                           if (box[box_num_1].y >= box_y1)
  992.                             {
  993.                               if (box_y1 > box[box_num_2].y)
  994.                                 {
  995.                                   box_delta_y=box[box_num_2].y-box[box_num_1].y;
  996.                                   box_delta_x=box[box_num_2].x-box[box_num_1].x;
  997.                                   box_y_offset=box_y1-box[box_num_1].y;
  998.                                   box_x_intercept=box[box_num_1].x;
  999.                                   box_x1=(int) ((box_delta_x*box_y_offset)
  1000.                                    /box_delta_y+box_x_intercept);
  1001.                                   if (intercept_count_mod_2 == 0)
  1002.                                     box_x2=box_x1;
  1003.                                   else
  1004.                                     {
  1005.                                       if (box_x1 < box_x2)
  1006.                                         {
  1007.                                           line_x1=box_x1;
  1008.                                           line_x2=box_x2;
  1009.                                         }
  1010.                                       else
  1011.                                         {
  1012.                                           line_x1=box_x2;
  1013.                                           line_x2=box_x1;
  1014.                                         }
  1015.                                       pset(&line_x1,&box_y1,shading);
  1016.                                       while (line_x1 < line_x2)
  1017.                                         {
  1018.                                           line_x1++;
  1019.                                           pset(&line_x1,&box_y1,shading);
  1020.                                         }
  1021.                                     }
  1022.                                   intercept_count_mod_2=1-intercept_count_mod_2;
  1023.                                 }
  1024.                             }
  1025.                           else
  1026.                             {
  1027.                               if (box_y1 <= box[box_num_2].y)
  1028.                                 {
  1029.                                   box_delta_y=box[box_num_2].y-box[box_num_1].y;
  1030.                                   box_delta_x=box[box_num_2].x-box[box_num_1].x;
  1031.                                   box_y_offset=box_y1-box[box_num_1].y;
  1032.                                   box_x_intercept=box[box_num_1].x;
  1033.                                   box_x1=(int) ((box_delta_x*box_y_offset)
  1034.                                    /box_delta_y+box_x_intercept);
  1035.                                   if (intercept_count_mod_2 == 0)
  1036.                                     box_x2=box_x1;
  1037.                                   else
  1038.                                     {
  1039.                                       if (box_x1 < box_x2)
  1040.                                         {
  1041.                                           line_x1=box_x1;
  1042.                                           line_x2=box_x2;
  1043.                                         }
  1044.                                       else
  1045.                                         {
  1046.                                           line_x1=box_x2;
  1047.                                           line_x2=box_x1;
  1048.                                         }
  1049.                                       pset(&line_x1,&box_y1,shading);
  1050.                                       while (line_x1 < line_x2)
  1051.                                         {
  1052.                                           line_x1++;
  1053.                                           pset(&line_x1,&box_y1,shading);
  1054.                                         }
  1055.                                     }
  1056.                                   intercept_count_mod_2=1-intercept_count_mod_2;
  1057.                                 }
  1058.                             }
  1059.                           box_num_2++;
  1060.                           if (box_num_2 >= 4)
  1061.                             box_num_2=0;
  1062.                         }
  1063.                     }
  1064.                   box_num_2=1;
  1065.                   for (box_num_1=0; box_num_1 < 4; ++box_num_1)
  1066.                     {
  1067.                       line_x1=box[box_num_1].x;
  1068.                       line_y1=box[box_num_1].y;
  1069.                       line_x2=box[box_num_2].x;
  1070.                       line_y2=box[box_num_2].y;
  1071.                       box_num_2++;
  1072.                       draw_line(&line_x1,&line_y1,&line_x2,&line_y2,shading);
  1073.                       if (box_num_2 >= 4)
  1074.                         box_num_2=0;
  1075.                     }
  1076.                   if ((prime_ptr->base_z == (char) 1)
  1077.                   &&  (prime_ptr->right->base_z == (char) 1)
  1078.                   &&  (prime_ptr->down->base_z == (char) 0)
  1079.                   &&  (prime_ptr->down->right->base_z == (char) 0)) 
  1080.                     {
  1081.                       if (prime_ptr->left != NULL)
  1082.                         {
  1083.                           if (prime_ptr->left->base_z == (char) 0)
  1084.                             {
  1085.                               shading='.';
  1086.                               line_x1=box[0].x;
  1087.                               line_y1=box[0].y;
  1088.                               line_x2=box[3].x;
  1089.                               line_y2=box[3].y;
  1090.                               draw_line(&line_x1,&line_y1,&line_x2,&line_y2,
  1091.                                shading);
  1092.                             }
  1093.                         }
  1094.                     }
  1095.                 }
  1096.              }
  1097.            prime_ptr=prime_ptr->lesser_x;
  1098.         }
  1099.     }
  1100. 
  1101.  
  1102.